\section[LLVM]{A infraestrutura de compiladores LLVM}

\begin{frame}
\textbf{A infraestrutura de compiladores LLVM}
\end{frame}

\begin{frame}
\frametitle{LLVM}
\begin{itemize}
  \item \emph{``Coleção modular de componentes reutilizáveis para implementação
  de compiladores e de ferramentas para análise e otimização de código. (...) é
  o futuro do desenvolvimento de compiladores de código aberto.''} (LATTNER; 
  ADVE, 2004)
  % projeto ambicioso, visto a existência do GCC
  
  \item Motivações:
  \begin{itemize}
    \item Gerenciar a complexidade dos compiladores estado-da-arte
    \item Ir além do compilador estático
    \item Habilitar a construção de um \emph{sistema de compilação}
  \end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Sistema de compilação}
\begin{itemize}
  \item O gerador de código deve realizar análises complexas e entender as
  dependências entre componentes
  % até recentemente, alguns compiladores modernos ainda não faziam otimizações
  % em tempo de ligação. Dessa maneira, ele pode entender com o código usa uma
  % determinada biblioteca, podendo otimizar o código gerado
  
  \item A otimização do código deve ocorrer ao longo do ciclo de vida
  % não somente em tempo de compilação
  
  \item Otimizações dinâmicas em tempo de execução
  % utiliza medições sobre o comportamento real do software
  
  \item Análise estática: correção de bugs, detecção de vazamentos de memória,
  etc.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{LLVM}
\begin{itemize}
  \item Suporte a construção das ferramentas mencionadas: compilador estático,
  máquina virtual com compilação \emph{JIT}, profilers, analisadores estáticos,
  etc.
  
  \item Várias arquiteturas: x86, x86-64, SparcV8, PowerPC, ARM, MSP430 e MIPS.
  
  \item Mais conhecido pelo \textbf{Clang}:
  % usuários finais
  \begin{itemize}
    \item Compilador C, C++, Object-C e Object-C++
    \item Utiliza toda a plataforma LLVM
    \item Performance comparável ao GCC
    % melhor tempo de compilação, código gerado com qualidade equivalente
  \end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Relevância do LLVM}
\begin{itemize}
  \item Plataforma robusta para implementar novas idéias
  % pesquisadores, projetistas de compiladores
  \item Grande base de contribuidores e usuários
\end{itemize}

\begin{figure}[htb]
  \centering
  \includegraphics[scale=0.45]{images/llvm-publicacoes}
  \textsf{\caption{Quantidade anual de trabalhos publicados que
          utilizam ou desenvolvem em topo do projeto LLVM.}}
\end{figure}

\end{frame}


\begin{frame}
\frametitle{Arquitetura do LLVM}
\begin{figure}[htb]
  \centering
  \includegraphics[scale=0.4]{images/llvm-arquitetura}
  \textsf{\caption{Arquitetura das ferramentas do projeto LLVM}}
\end{figure}
\end{frame}


\begin{frame}
\frametitle{Representação Intermediária}
\framesubtitle{LLVM-IR}
\begin{itemize}
  \item Unidade central do LLVM e deste trabalho
  \item Compromisso: alto nível $\times$ baixo nível
  \item Objetivos:
  \begin{itemize}
    \item Independente de linguagem
    \item Suporte a diversas análises e otimizações
    \item Flexibilidade: 3 representações
    \item Fortemente tipada
    \item Instruções de 3 endereços
    \item Usa saltos explícitos para controle de fluxo
  \end{itemize}
  
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Forma SSA}
\framesubtitle{Static Single Assignment}
\begin{itemize}
  \item Registradores virtuais
  \item Facilita manipulação de relações \emph{definição-uso}
\end{itemize}

\begin{figure}[ht]
  \centering              
  \subfloat[Exemplo 1]
  {\includegraphics[scale=0.5]{images/ssa-exemplo1}}
  \subfloat[Exemplo 2]
  {\includegraphics[scale=0.5]{images/ssa-exemplo2}}
\end{figure}
\end{frame}


\begin{frame}[fragile]
\frametitle{Exemplo LLVM-IR}
\begin{columns}[c]
\column{.5\textwidth}

\footnotesize
\begin{verbatim}
int f(int* n) {
  if (*n <= 3)
    return *n + 1;
  else
    return *n - 1;
}

int main(void) {
  int x = 4;
  return f(&x);
}
\end{verbatim}

\column{.5\textwidth}
\tiny
\begin{verbatim}
define i32 @f(i32* %n) nounwind {
entry:
  %retval = alloca i32
  %tmp1 = load i32* %n
  %cmp = icmp sle i32 %tmp1, 3
  br i1 %cmp, label %if.then, label %if.else

if.then:
  %add = add nsw i32 %tmp1, 1
  store i32 %add, i32* %retval
  br label %return

if.else:
  %sub = sub nsw i32 %tmp1, 1
  store i32 %sub, i32* %retval
  br label %return

return:
  %0 = load i32* %retval
  ret i32 %0
}

define i32 @main() nounwind {
entry:
  %x = alloca i32
  store i32 4, i32* %x
  %call = call i32 @f(i32* %x)
  ret i32 %call
}
\end{verbatim}

\end{columns}
\end{frame}

\begin{frame}
\frametitle{Framework de Geração de Código}
\begin{itemize}
  \item Componentes responsáveis pela tradução da LLVM-IR
  \item 3 camadas:
  \begin{itemize}
    \item Classes que modelam o código de máquina: instruções, funções,
    registradores, ...
    \item Algoritmos independentes do alvo: análises, otimizações e outros (ex:
    alocador de registradores)
    \item O código específico a cada alvo (\emph{backends}).
  \end{itemize}
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Framework de Geração de Código}
\begin{itemize}
  \item O processo de geração é dividido em 7 passos:
  \begin{enumerate}
    \item \alert{Seleção de instruções}
    \item Escalonamento de instruções
    \item Otimizações na forma SSA
    \item Alocação de registradores
    \item \alert{Emissão do prólogo e do epílogo}
    \item Otimizações finais
    \item \alert{Emissão do código}
  \end{enumerate}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Seleção de Instruções}
\begin{itemize}
  \item Foco do módulo RISCO para o LLVM
  \item Representação do código como DAG
  \item Reescrita do grafo iterativamente
  \begin{itemize}
    \item \alert{Problema NP-Completo}
    \item Algoritmo guloso com heurísticas próprias (KOES; GOLDSTEIN, 2008)
  \end{itemize}
\end{itemize}
\end{frame}